package cn.fantasy.algorithm;

/**
 * 数组中重复的数字
 * 在一个长度为n的数组nums里的所有数字都在0~n-1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道重复了几次，
 * 请找出数组中任意一个重复的数字。
 * <p>
 * 示例：输入[1, 2, 1, 3, 2]
 * 输出：1或2
 */
public class ArrayDuplicateNumber {
    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 4, 1, 3, 5};
        int c = findRepeatNumber2(arr);
        System.out.println(c);
    }

    /**
     * 方案一 空间优先：原地排序法
     * 遍历数组，将遍历的数试探放入值正确位置，如果正确位置已经有过正确数了，且不是当前位置，说明发现了重复数了，退出
     * 如果正确位置不是正确值，将正确值交换到正确位置
     *
     * @param nums
     * @return int
     */
    public static int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (n == nums[n] && n != i) return n;
            int tmp = nums[i];
            nums[i] = nums[n];
            nums[n] = tmp;
        }
        return -1;
    }

    /**
     * 时间优先：字典
     * 用两个字节的boolean 的数组，占用空间小
     *
     * @param nums
     * @return
     */
    public static int findRepeatNumber2(int[] nums) {
        boolean compare[] = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (compare[nums[i]]) return nums[i];
            compare[nums[i]] = true;
        }
        return -1;
    }
}
